package com.jwetherell.my.problems.misc;

/**
 * http://www.geeksforgeeks.org/reverse-words-in-a-given-string
 * 
 * Example: Let the input string be “i like this program very much”. The
 * function should change the string to “much very program this like i”
 * 
 * Time Complexity: O(n)
 */
public class ReverseWordsInAString {

	public static void main(String[] args) {
		String input = " i like this program very much";
		System.out.println("Input: '" + input + "'");
		
		String output = new ReverseWordsInAString().reverseWordsInAString(input);
		System.out.println("Output: '" + output + "'");
	}

	private String reverseWordsInAString(String input) {
		return reverseWholeString(reverseIndividualWords(input.toCharArray()));
	}


	private char[] reverseIndividualWords(char[] input) {
		
		int i = 0;
		for(int k = 0; k < input.length; k++) {
			if (input[k]==' ') {
				reverse(input, i, k-1);
				i = k+1;
			} else if (k==(input.length-1)) {
				reverse(input, i, k);
			}
		}
		
		return input;
	}
	
	private String reverseWholeString(char[] input) {
		return String.copyValueOf(reverse(input, 0, input.length-1));
	}

	private char[] reverse (char[] input, int i, int j) {
		char temp;
		while (i < j) {
			temp = input[i];
			input[i] = input[j];
			input[j] = temp;
			i++;
			j--;
		}
		return input;
	}
}
